//
// Created by liushuai on 2020/5/6.
//

#pragma once
#include <algorithm>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

#include "Node.h"
#include "TreeNode.h"
bool isSymmetric(TreeNode *root1, TreeNode *root2);
bool isSymmetric(TreeNode *root);
bool isSameTree(TreeNode *root1, TreeNode *root2);
bool isValidBST(TreeNode *root);
bool isValidBST(TreeNode *root, long min, long max);
TreeNode *mirrorTreeRecursive(TreeNode *root);
TreeNode *mirrorTree(TreeNode *root);
bool isContainSubTree(TreeNode *root1, TreeNode *root2);
TreeNode *sortedArrayToBST(std::vector<int> &nums);
TreeNode *sortedArrayToBST(std::vector<int> &nums, int l, int r);
int minDepth(TreeNode *root);
int maxDepth(TreeNode *root);
int minDepthWithBFS(TreeNode *root);
std::vector<TreeNode *> getPath(TreeNode *root, TreeNode *target);
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q);
bool hasPathSum(TreeNode *root, int sum);
int maxDepth(Node *root);
std::vector<std::vector<int>> levelOrderRecord(TreeNode *root);
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode *root);
TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2);
bool isCompleteTree(TreeNode *root);
std::vector<std::string> binaryTreePaths(TreeNode *root);
int sumNumbers(TreeNode *root);
int binaryMaxTreePathsSum(TreeNode *root);
std::vector<int> travelTree(TreeNode *root);
void flatten(TreeNode *root);
int maxPathSum(TreeNode *root);
int kthLargest(TreeNode *root, int k);
TreeNode *buildTree(std::vector<int> &preorder, std::vector<int> &inorder);
int widthOfBinaryTree(TreeNode *root);
int dfsMaxPathSum(TreeNode *root);
int dfsMaxPathSum(TreeNode *root, int path_sum);
TreeNode *convertBST(TreeNode *root);
